package com.hyper_yang.algorithmRecord.dynamicProgramming;

// 0-1 背包问题
public class KnapsackProblem {
    // 动态规划实现 (返回当前最大价值)

    /**
     * @param capacity 容量
     * @param weights  物品重量数组
     * @param values   物品价值数组
     * @return
     */
    public int maxValue1(int capacity, int[] weights, int[] values) {
        int n = weights.length; // 物品数量
        // 定义状态
        int[][] dp = new int[n + 1][capacity + 1];
        // 遍历所有子问题，依次计算状态  （有 i个物品，最大容量为 j时的最大价值）
        for (int i = 1; i <= n; i++) { // i=0 没有物品不计算价值
            for (int j = 0; j <= capacity; j++) {
                // 放的下
                if (j >= weights[i - 1])
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                    // 放不下
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][capacity];
    }

    // 空间优化: （滚动数组）
    public int maxValue(int capacity, int[] weights, int[] values) {
        int n = weights.length;
        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = capacity; j > 0; j--) {
//            for (int j = 0; j <= capacity; j++) { 这是错误的 会导致重复计算已计算过的物品。   相当于 东西可以重复放
                if (j >= weights[i - 1]) {
                    dp[j] = Math.max(dp[j], dp[j - weights[i - 1]] + values[i - 1]);
                }
            }
        }
        return dp[capacity];
    }

    public static void main(String[] args) {
        KnapsackProblem napsack = new KnapsackProblem();
        System.out.println(napsack.maxValue(30, new int[]{30, 10, 20}, new int[]{28, 20, 10}));
        System.out.println(napsack.maxValue(150, new int[]{35, 30, 60, 50, 40, 10, 25}, new int[]{10, 40, 30, 50, 35, 40, 30}));
    }
}
